package com.kk.datastructure.recursion;

/**
 * title: 八皇后问题--递归解决
 * @author 阿K
 * 2020年12月6日 下午2:04:51 
 */
public class Queue8 {

	// max表示共有多少个皇后
	int max = 8;
	// array, 保存每次皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
	int[] array = new int[max];
	static int count = 0;
	static int bif = 0;
	public static void main(String[] args) {
		// 测试
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.printf("一共有%d解法\n", count);
		System.out.printf("一共判断冲突的次数%d次", bif); 
	}

	/**
	 * 放置第n个皇后 特别注意： check 是 每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯
	 * 
	 * @param n
	 */
	private void check(int n) {
		if (n == max) {// n = 8 , 其实8个皇后就既然放好,准备放第九个
			print();
			return;
		}
		// 依次放入皇后，并判断是否冲突
		for (int i = 0; i < max; i++) {
			// 先把当前这个(行)皇后 n , 放到该行的第1列，可以理解n 就是行
			array[n] = i;
			// 判断当放置第n个皇后到i列时，是否冲突
			if (judge(n))
				// 不冲突
				// 接着放n+1个皇后,即开始递归
				check(n + 1);
			// 如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置
		}
	}

	/**
	 * 查看皇后是否冲突
	 * 
	 * @param n 第几个皇后，或者是第几行皇后。eg:array[3] = val,意思是第四行皇后的值为，val列
	 * @return
	 */
	private boolean judge(int n) {
		bif++;
		for (int i = 0; i < n; i++) {
			// 1、array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列
			// 2、Math.abs(n-i) == Math.abs(array[n] - array[i])
			// 表示判断第n个皇后是否和第i皇后是否在同一斜线（这个公式不是固定，
			// 根据数组的规则推导--也只适应于这样设计的数组）
			// 3.不用判断是否同一行，因为在设计的时候，通过数组角标代表行，N每次都在递增（不会出现在同一行的结果）
			if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
				return false;
			}
		}
		return true;
	}

	// 输出皇后的摆放（用于成立的结果）
	private void print() {
		count++;
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
}
